package day12;

import java.util.*;

/**
 * 给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
 *
 * 每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
 *
 * i + 1 需满足：i + 1 < arr.length
 * i - 1 需满足：i - 1 >= 0
 * j 需满足：arr[i] == arr[j] 且 i != j
 * 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
 *
 * 注意：任何时候你都不能跳到数组外面。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
 * 输出：3
 * 解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
 * 示例 2：
 *
 * 输入：arr = [7]
 * 输出：0
 * 解释：一开始就在最后一个元素处，所以你不需要跳跃。
 * 示例 3：
 *
 * 输入：arr = [7,6,9,6,9,6,9,7]
 * 输出：1
 * 解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
 */
public class Solution4 {
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> hm = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            hm.putIfAbsent(arr[i],new ArrayList<>());
            hm.get(arr[i]).add(i);
        }
        Set<Integer> hs = new HashSet<>();
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0,0});
        hs.add(0);
        while (!queue.isEmpty()){
            int []idxStep = queue.poll();
            int idx = idxStep[0],step = idxStep[1];
            if(idx == arr.length-1){
                return step;
            }
            int v = arr[idx];
            step++;
            if(hm.containsKey(v)){
                for (Integer integer : hm.get(v)) {
                    if(hs.add(integer)){
                        queue.offer(new int[]{integer,step});
                    }
                }
                hm.remove(v);
            }
            if(idx + 1<arr.length&&hs.add(idx+1)){
                queue.offer(new int[]{idx+1,step});
            }
            if(idx-1>=0&&hs.add(idx-1)){
                queue.offer(new int[]{idx-1,step});
            }
        }
        return -1;
    }
}
